/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution86 {

    public static void main(String args[]) {
        Solution86 s = new Solution86();
        ListNode a = new ListNode(4);
        ListNode b = new ListNode(1);
        ListNode c = new ListNode(2);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(1);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        System.out.println(s.partition(e, 3));
    }

    public ListNode partition(ListNode head, int x) {
        ListNode head1 = null;
        ListNode head2 = null;
        ListNode cur1 = null;
        ListNode cur2 = null;

        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (head1 == null) {
                    head1 = cur;
                    cur1 = cur;
                } else {
                    cur1.next = cur;
                    cur1 = cur1.next;
                }
            } else {
                if (head2 == null) {
                    head2 = cur;
                    cur2 = cur;
                } else {
                    cur2.next = cur;
                    cur2 = cur2.next;
                }
            }
            cur = cur.next;
        }
        if (cur1 != null) {
            cur1.next = head2;
        }
        if(cur2 != null) {
            cur2.next = null;
        }
        return head1 == null && head2 != null ? head2 : head1;
    }
}
